/**
 * Author  zxy
 * Date  2023/8/12 16:24
 */

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Question2 {
    static int ret = Integer.MAX_VALUE;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int T = in.nextInt();

        for (int i = 0; i < T; i++) {
            ret = Integer.MAX_VALUE;

            int n = in.nextInt();

            int[] arr = new int[n];
            for (int j = 0; j < n; j++) {
                arr[j] = in.nextInt();
            }

            func (0, 0, 0, arr, 0);

            System.out.println(ret);
        }

    }

    public static void func (int left, int right, int cur, int[] arr, int index) {
        if (index == arr.length) {
            ret = Math.min(ret, right - left);
            return ;
        }

        int temp;

        // 1: 左移
        temp = cur - arr[index];
        if (temp >= left) {
            func (left, right, temp, arr, index + 1);
        }
        else {
            func (temp, right, temp, arr, index + 1);
        }

        // 2: 右移
        temp = cur + arr[index];
        if (temp <= right) {
            func (left, right, temp, arr, index + 1);
        }
        else {
            func (left, temp, temp, arr, index + 1);
        }
    }
}